package SeqList;

//车厢类
class Node{
    int data;
    Node next;

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    public Node(int data) {
        this.data = data;
    }

    public Node(Node next) {
        this.next = next;
    }
}

public class SingleLinkList {
    private int size;
    private Node head;
    //单链表的头插法
    public void addFirst(int data){
   //要往火车头部添加元素，要先判断火车是否为空
        if(head==null)//?
        {
            Node node=new Node(data);
            head=node;
            size++;
        }else{
            //说明当前已经存在元素，只需要正常操作
            Node node=new Node(data);
            node.next=head;
            head=node;
            size++;
        }
    }
    //在火车的中部添加元素
    public void addIndex(int index,int data){
        //先判断index的合法性
        if(index<0||index>size)
        {
            System.out.println("add index illegal");
            return;
        }
        //如果此时Index==0
        if(index==0)
        {
          addFirst(data);
          return;
        }
        Node node=new Node(data);
        //prev是当前需要添加新的节点的前驱
        Node prev=head;
        for (int i = 0; i < index-1; i++) {
          prev=prev.next;
        }
        node.next=prev.next;
        prev.next=node;
        size++;
    }
    public void addLast(int data)
    {
        addIndex(size,data);
    }
    //index范围控制
    private boolean rangeCheck(int index)
    {
        if(index<0||index>=size)
        {
            return false;
        }
        return true;
    }
    //查询index位置的节点数据
    public int getData(int index)
    {
     if(rangeCheck(index))
     {
         Node node=head;
         for (int i = 0; i <index ; i++) {
             node=node.next;
         }
         //此时node指向需要查找到元素的索引
         int data=node.data;
         return data;
     }else{
         System.out.println("get index illegal");
         return -1;
     }
    }
    //看单链表中是否包含此元素
    public boolean contains(int data)
    {
        Node node=head;
        while(node!=null)
        {
            if(node.data==data)
            {
                System.out.println("找到元素！");
                return true;
            }
            node=node.next;
        }
        return  false;
    }
    //修改index的值并返回原数值
    public int set(int index,int data)
    {
        if(rangeCheck(index))
        {
          Node node=head;
            for (int i = 0; i <index; i++) {
                node=node.next;
            }
            int oldData=node.data;
            int newData=data;
            return oldData;
        }
        else{
            System.out.println("set data illegal");
            return -1;
        }
    }


    //删除首元素
    public void removeFirst(){
       if(head==null)
       {
           System.out.println("无元素，无法删除");
       }else {
           Node node=head;
           head=head.next;
           node.next=null;
           size--;
       }
    }
    public void removeIndex(int index)
    {
        //判断边界条件
        if(rangeCheck(index)){
            if(index==0){
                removeFirst();
            }else{
                //此时index处于中间位置
                Node prev=head;
                for (int i = 0; i <index-1 ; i++) {
                  prev=prev.next;
                }
                Node node=prev.next;
                prev.next=node.next;
                node.next=null;
                size--;
            }
        }else{
            System.out.println("删除位置不合法！");
        }
    }
    //删除制定元素的第一个节点【1,2,2,3,5】删除第一个2即可
    public void removeValueOnce(int data){
        //先要判断头节点
        if(head.data==data)
        {
            removeFirst();
        }else{
            //此时头结点一定不是要删除的节点
            //从头节点开始找
            Node prev=head;
            //不知道要找多少次，所以我们用while
          while(prev.next!=null)
          {
              //此时prev的下一个节点一定是待删除的节点
              if(prev.next.data==data)
              {
                  Node node=prev.next;
                  prev.next=node.next;
                  node.next=null;
                  size--;
                break;
              }else{
                  prev=prev.next;
              }

          }
        }
    }
//要删除同样的值的多个元素
    public void removeAllValue(int data){
        //先判断头节点的情况
        //头结点以及之后出现了很很多连续待删除的节点
        while(head!=null&&head.data==data)
        {
            Node node=head;
            head=head.next;
            node.next=null;
            size--;
        }
        //此时head一定不是待删除的元素
        //head.data！=data
        //看删除完头节点之后单链表是否为空
        if(head==null)
        {
           return;
        }
        else{
            //此时头节点已经全部处理完毕,并且链表也不为空，看中间的元素是否有待删除的元素
            Node prev=head;
            while(prev.next!=null)
            {
                Node node=prev.next;
                if(node.data==data)
                {
                  // node就是待删除的元素
//                    Node node=prev.next;
                    prev.next=node.next;
                    node.next=null;
                    size--;
                }else {
                    prev=prev.next;
                }
            }
        }
    }
    public String toString()
    {
        String ret=" ";
        Node node=head;
        while(node!=null)
        {
            ret+=node.data+"->";
            node=node.next;
        }
        ret+="NULL";
        return ret;
    }
    public static void main(String[] args) {
      SingleLinkList singleLinkList=new SingleLinkList();
      singleLinkList.addLast(3);
      singleLinkList.addLast(2);
      singleLinkList.addLast(3);
      singleLinkList.addLast(2);
      singleLinkList.addFirst(2);
      singleLinkList.addFirst(2);
      singleLinkList.addFirst(2);
      singleLinkList.addIndex(1,2);
        System.out.println(singleLinkList);
//      singleLinkList.removeIndex(2);
//
//        System.out.println(singleLinkList);
//        singleLinkList.removeIndex(1);
//        System.out.println(singleLinkList);
//        singleLinkList.removeValueOnce(3);
//        System.out.println(singleLinkList);
        singleLinkList.removeAllValue(2);
        System.out.println(singleLinkList);
    }
}
